import javafx.scene.transform.Scale;

import java.util.*;

class LFUCache {
    Map<Integer,Integer> map;
    int capacity;
    public LFUCache(int capacity) {
        this.capacity=capacity;
        map=new LinkedHashMap<>();
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        int val=map.get(key);
        map.remove(key);
        map.put(key,val);
        return val;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            map.remove(key);
            map.put(key,value);
            return;
        }
        map.put(key,value);
        if(map.size()>capacity){
            map.remove(map.entrySet().iterator().next().getKey());
        }
    }
}









class LRUCache1 {
    Map<Integer,Integer> map;
    int capacity;
    public LRUCache1(int capacity) {
        map=new LinkedHashMap<>();
        this.capacity=capacity;
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        int val=map.get(key);
        map.remove(key);
        map.put(key,val);
        return val;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            map.remove(key);
            map.put(key,value);
            return;
        }
        map.put(key,value);
        if(map.size()>capacity){
            map.remove(map.entrySet().iterator().next().getKey());
        }
    }
}





class Solution {
    Map<Integer,List<Integer>> map;
    Random random;
    public Solution(int[] nums) {
        random=new Random();
        map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            List<Integer> list=map.getOrDefault(nums[i],new ArrayList<>());
            list.add(i);
            map.put(nums[i],list);
        }
    }

    public int pick(int target) {
        List<Integer> list=map.get(target);
        int size=list.size();
        return list.get(random.nextInt(size));
    }
}






public class project {
    public int numberOfBoomerangs(int[][] points) {
        int ret=0;
        for(int[] p:points){
            Map<Integer,Integer> map=new HashMap<>();
            for(int[] q : points){
                int tmp=(p[0]-q[0])*(p[0]-q[0])+(p[1]-q[1])*(p[1]-q[1]);
                map.put(tmp,map.getOrDefault(tmp,0)+1);
            }
            for(Map.Entry<Integer,Integer> entry:map.entrySet()){
                int tmp=entry.getValue();
                ret+=tmp*(tmp-1);
            }
        }
        return ret;
    }
















    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        Map<Integer, Set<Integer>> map=new HashMap<>();
        for(int[] log : logs){
            Set<Integer> set=map.getOrDefault(log[0],new HashSet<>());
            set.add(log[1]);
            map.put(log[0],set);
        }
        int[] ret=new int[k];
        for(Map.Entry<Integer,Set<Integer>> entry : map.entrySet()){
            int size=entry.getValue().size();
            ret[size-1]++;
        }
        return ret;
    }


















    public int[] findBall(int[][] grid) {
        int len=grid[0].length;
        int[] arr=new int[len];
        for(int i=0;i<len;i++){
            int col=i;
            for(int[] g : grid){
                int val=g[col];
                col+=val;
                if(col<0||col==len||val!=g[col]){
                    col=-1;
                    break;
                }
            }
            arr[i]=col;
        }
        return arr;
    }
























    public int[] findBall1(int[][] grid) {
        //获取长度
        int len=grid[0].length;

        //返回结果
        int[] arr=new int[len];

        //遍历每一个球
        for(int index=0;index<len;index++){

            //记录球的起始位置
            int col=index;

            //遍历每一行
            for(int[] g : grid){

                //当前行，球要经过的是1还是-1；
                int val=g[col];

                //球是向前一行还是向后一行
                col+=val;

                //判断球是否走到了左边框或有边框，或掉到了V型死角
                if(col<0||col==len||g[col]!=val){

                    //死角返回-1
                    col=-1;
                    break;
                }
            }

            //每个球的最终结果放入数组中。
            arr[index]=col;
        }
        return arr;
    }
}
